package org.example.algorithm.binarytree;

import org.example.algorithm.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 返回二叉树最大路径和路径序列
 */

public class MaxPathSumReturnPathSolution {
    private static List<TreeNode> treeNodeList = new ArrayList<>();
    private static int sum;

    public static void main(String[] args) {
        TreeNode tree = new TreeNode(3);
        tree.left = new TreeNode(9);
        tree.left.right = new TreeNode(11);
        tree.left.right.left = new TreeNode(31);
        tree.right = new TreeNode(20);
        tree.right.left = new TreeNode(15);
        tree.right.right = new TreeNode(7);
        tree.right.left.left = new TreeNode(9);
        tree.right.left.right = new TreeNode(80);
        maxSidePath(tree);
        System.out.println("最大路径和为:" + sum);
        System.out.println("开始打印路径信息:");
        for (TreeNode treeNode: treeNodeList) {
            System.out.println(treeNode.val);
        }
    }

    public static List<TreeNode> maxSidePath(TreeNode node) {
        List<TreeNode> result = new ArrayList<>();
        if (node == null) {
            return result;
        }
        List<TreeNode> leftPath = maxSidePath(node.left);
        List<TreeNode> rightPath = maxSidePath(node.right);
        int leftSum = sumTreeNode(leftPath);
        int rightSum = sumTreeNode(rightPath);
        if (leftSum > rightSum) {
            if (leftSum + node.val > 0) {
                result.add(node);
                result.addAll(leftPath);
            }
        } else {
            if (rightSum + node.val > 0) {
                result.add(node);
                result.addAll(rightPath);
            }
        }
        if (leftSum + rightSum + node.val > sum) {
            sum = leftSum + rightSum + node.val;
            treeNodeList.clear();
            Collections.reverse(leftPath);
            treeNodeList.addAll(leftPath);
            treeNodeList.add(node);
            treeNodeList.addAll(rightPath);
        }
        return result;
    }

    public static int sumTreeNode(List<TreeNode> nodeList) {
        return Math.toIntExact(nodeList.stream().mapToInt(item -> item.val).sum());
    }

}
